# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# class Solution(object):
#     def reverseList(self, head):
#         """
#         :type head: ListNode
#         :rtype: ListNode
#         """
#         if not head or not head.next:
#             return head
#         rev_nodes = ListNode(head.val)
#         while head.next:
#             head = head.next
#             cur_node = ListNode(head.val)
#             cur_node.next = rev_nodes
#             rev_nodes = cur_node
#         return rev_nodes
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        pred = None
        while head:
            nxt = head.next
            head.next = pred
            pred = head
            head = nxt
        return pred

class Solution(object):
    def reverseList(self, head):
        def helper(head, pred):
            if head:
                nxt = head.next
                head.next = pred
                return helper(nxt, head)
            else:
                return pred
        return helper(head, None)